package cn.lbl.face.niuke;

public class 二分查找 {
    /*
    5,4,[1,2,4,4,5]

     */
    public static int upper_bound_ (int n, int v, int[] a) {
        // write code here
        int start=0;
        int end=n-1;
        int index;
        while (start<end){
        index = start+(end-start) / 2;
        if (a[index] == v) {
            return index+1;
        }else if (a[index] > v) {
            end=index;
        }else if (a[index] < v){
            start=index;
        }
        }
        return n+1;
    }
/*
    10,2,[1,1,2,3,7,7,7,9,9,10]
 */
    public static void main(String[] args) {
        System.out.println(upper_bound_(100,1,new int[]{2,3,4,4,4,7,7,8,10,10,11,12,13,14,15,15,17,18,19,23,24,24,24,24,25,26,26,26,27,27,28,29,29,30,33,36,38,38,40,40,41,43,43,43,44,46,46,47,51,52,52,53,54,56,57,57,57,58,58,61,61,61,62,64,64,66,66,67,67,67,70,72,74,74,74,75,75,78,78,78,79,79,80,83,83,83,83,84,84,86,88,89,89,90,91,91,92,93,93,96}));
    }
}
